#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <set>

#define flr(x,l,r) for (int x = l; x <= r; ++ x)
#define frl(x,r,l) for (int x = r; x >= l; -- x)
#define fmp(x,t) for (int x = h[t]; ~x; x = ne[x])
#define LL long long 
#define mt memset 
#define szf sizeof
#define INF 0x3f3f3f3f
#define in(x) scanf("%d", &x)
#define out(x) printf("%d", x)
#define inll(x) scanf("%lld", &x)
#define outll(x) printf("%lld", x)
#define pn printf("\n")
#define con continue
#define bk break
#define vc vector
#define pb push_back
#define sz size
#define PII pair<int, int>
#define x first
#define y second
#define P_q priority_queue
#define ft front
#define pf push_front
#define popf pop_front
#define it insert
#define ct count

using namespace std;

const int N = 1010, M = 2e4 + 10;

struct Ver {
    int id, type, distance;
    bool operator> (const Ver& W) const {
        return distance > W.distance;
    }
};
int n, m, S, F;;
int h[N], e[M], w[M], ne[M], idx;
int dist[N][2], cnt[N][2];
bool st[N][2];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra() {
    mt(st, 0, szf st);
    mt(dist, 0x3f, szf dist);
    mt(cnt, 0, szf cnt);
    dist[S][0] = 0, cnt[S][0] = 1;
    
    P_q<Ver, vc<Ver>, greater<Ver>> heap;
    heap.push({S, 0, 0});
    
    while (heap.sz()) {
        Ver t = heap.top();
        heap.pop();
        
        int ver = t.id, type = t.type, distance = t.distance, count = cnt[ver][type];
        if (st[ver][type]) con;
        st[ver][type] = true;
        
        fmp (i, ver) {
            int j = e[i];
            if (dist[j][0] > distance + w[i]) {
                dist[j][1] = dist[j][0], cnt[j][1] = cnt[j][0];
                heap.push({j, 1, dist[j][1]});
                dist[j][0] = distance + w[i], cnt[j][0] = count;
                heap.push({j, 0, dist[j][0]});
            }
            else if (dist[j][0] == distance + w[i]) cnt[j][0] += count;
            else if (dist[j][1] > distance + w[i]) {
                dist[j][1] = distance + w[i], cnt[j][1] = count;
                heap.push({j, 1, dist[j][1]});
            }
            else if (dist[j][1] == distance + w[i]) cnt[j][1] += count;
        }
    }
    
    if (dist[F][0] + 1 == dist[F][1]) cnt[F][0] += cnt[F][1];
    
    return cnt[F][0];
}

int main() {
    int T;
    in(T);
    
    while (T -- ) {
        in(n), in(m);
        
        mt(h, -1, szf h);
        idx = 0;
        while (m -- ) {
            int a, b, c;
            in(a), in(b), in(c);
            add(a, b, c);
        }
        
        in(S), in(F);
        
        out(dijkstra()), pn;
    }
    
    return 0;
}